This invention relates to the field of switching, and particularly to a non-blocking switching network which has an unexpectedly low number of crosspoint switches and can be used to replace selector switch banks in a step-by-step telephone switching office.
The cost of a space division switching matrix is largely dependent on the number of crosspoints required to switch input sources (inputs) to destinations (outputs). A crossbar switch, for instance, utilizes a number of crosspoint switches which is equal to the number of inputs multiplied by the number of outputs. For an equal number of inputs and outputs n, the number of crosspoint switches is n.sup.2. Clearly as the number of inputs and outputs increases, the number of crosspoints increases disproportionately. For a large number of inputs and outputs the size of the crossbar switch would not be economic, and crosspoint switch reducing schemes have been designed, some in which certain degrees of blocking were tolerated.
Networks have been designed to provide interconnection between large numbers of inputs and outputs, with a smaller number of crosspoints than would otherwise be required by the determination noted above. As described in SCIENTIFIC AMERICAN, Volume 238 No. 6, dated June 1978 in an article on COMPLEXITY THEORY by Nicholas Pippenger, page 114 ff., a more efficient design was discovered in the 1950's by Charles Clos of Bell Laboratories. In Clos's design a network that can handle up to n calls at the same time, without blocking, can be constructed with about 6n.sup.1.5 crosspoint switches. It appears that when n is 36 or greater, the number of switches is always less than n.sup.2.
The same article in Scientific American notes that L. A. Bassalygo and M. S. Pinsker of the INSTITUTE FOR PROBLEMS OF INFORMATION TRANSMISSION, in Moscow determined that theoretically sparse crossbars can be built to provide networks with fewer switches than the network designed by Clos. The networks proposed by Bassalygo and Pinsker suggests that for a K-by-K subnetwork, only 12 K switches are required, whereas in a normal crossbar subnetwork K.sup.2 switches are required. Unfortunately, while Bassalygo and Pinsker theoretically showed that such networks are possible, they did not describe any structural embodiments by which the theory could be realized in practice.
Sparse crossbars are crossbar switches in which a number of crosspoints have been removed, yet which do not affect the blocking probability of the network.
The Scientific American article notes that there are some solutions to the Bassalygo and Pinsker proposals which will not work, and that indeed it would take an impossibly long time to test all solutions and determine which are blocking to what certain degree and which are not.
The present invention, on the other hand, is a switching subnetwork which may be used in place of a crossbar switch, or in place of a selector switch in a step-by-step telephone switching network, which is non-blocking, yet which utilizes a substantially reduced number of switches than might otherwise be expected. For example, in a network having ten inputs to be switched to 100 outputs, a normal crossbar switch would require 1,000 crosspoints, yet the present invention requires only 600. Clearly the cost of such subnetworks is substantially reduced.